package com.hot100;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class h017 {
    Map<Character,char[]> map = new HashMap<Character,char[]>(){{
        put('2',new char[]{'a','b','c'});
        put('3',new char[]{'d','e','f'});
        put('4',new char[]{'g','h','i'});
        put('5',new char[]{'j','k','l'});
        put('6',new char[]{'m','n','o'});
        put('7',new char[]{'p','q','r','s'});
        put('8',new char[]{'t','u','v'});
        put('9',new char[]{'w','x','y','z'});
    }};
    List<String> res = new ArrayList<>();
    String digits;
    StringBuilder sb = new StringBuilder();
    int len = 0;

    public List<String> letterCombinations(String digits) {
        this.digits = digits;
        len = digits.length();
        if (len == 0) return res;
        recur(0);
        return res;
    }

    public void recur(int index){
        char[] nums = map.get(digits.charAt(index));
        for (int i=0;i<nums.length;i++){
            sb.append(nums[i]);
            if (index < len-1) recur(index+1);
            if (index == len-1){
                res.add(sb.toString());
            }
            sb.delete(index,sb.length());
        }
    }
}